#include <stdio.h>
void print_array(int arr[], int size) {
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

void insertion_sort(int unsorted_array[], int num_elements) {
	for (int j = 1; j < num_elements; j++) {
		int key = unsorted_array[j];
		int i = j - 1;
		while (i >= 0 && key < unsorted_array[i]) {
			unsorted_array[i + 1] = unsorted_array[i];
			i--;
		}
		unsorted_array[i + 1] = key;
		print_array(unsorted_array, num_elements);
	}
}

int partition(int L[], int low, int  high, int total_num_elements) {
	int temp = L[low];
	int pivot = L[low];
	while (low < high) {
		while (low < high && L[high] >= pivot) {
			--high;
		}
		L[low] = L[high];
		while (low < high && L[low] <= pivot) {
			++low;
		}
		L[high] = L[low];
	}
	L[low] = temp;
	print_array(L, total_num_elements);
	return low;
}
void QSort(int L[], int low, int  high, int total_num_elements) {
	if (low < high) {
		int  pivotpos = partition(L, low, high, total_num_elements);
		
		QSort(L, low, pivotpos - 1, total_num_elements);
		QSort(L, pivotpos + 1, high, total_num_elements);
		
	}
}

void quick_sort(int unsorted_array[], int num_elements) {
	int low = 0, high = num_elements - 1;
	QSort(unsorted_array, low, high, num_elements);
}


void max_heap_down(int a[], int start, int end)
{
	int c = start;
	int l = 2 * c + 1;
	int tmp = a[c];
	for (; l <= end; c = l, l = 2 * l + 1)
	{
		if (l < end && a[l] < a[l + 1])
			l++;
		if (tmp >= a[l])
			break;
		else
		{
			a[c] = a[l];
			a[l] = tmp;
		}
	}
}
void heap_sort(int unsorted_array[], int num_elements) {
	int i;
	int swap;
	for (i = num_elements / 2 - 1; i >= 0; i--)
		max_heap_down(unsorted_array, i, num_elements - 1);
	for (i = num_elements - 1; i > 0; i--)
	{
		swap = unsorted_array[i];
		unsorted_array[i] = unsorted_array[0];
		unsorted_array[0] = swap;
		print_array(unsorted_array, num_elements);
		max_heap_down(unsorted_array, 0, i - 1);
	}
	
}
void main() {
	int test[10] = { 4,3,2,1 };
	insertion_sort(test, 4);
	printf("\n");
	int test1[10] = { 3,1,2,5,4 };
	QSort(test1, 0, 4, 5);
	printf("\n");
	int test2[10] = { 10,60,12,40,30,8,70 };
	heap_sort(test2, 7);
}	